package com.fanshuai.set;

import java.util.Iterator;

public class HashSet<E extends Comparable<E>> implements Set<E> {
    public class Node<E> {
        public E data;
        public Node<E> next;

        public Node(E data) {
            this.data = data;
            this.next = null;
        }
    }

    private Node<E>[] table;
    private int size;

    private int defaultSize = 16;
    private double loadFactor = 0.75;


    public HashSet() {
        table = (Node<E>[]) new Node[defaultSize];
        size = 0;
    }

    public HashSet(int size) {
        table = (Node<E>[]) new Node[size];
        this.size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    private int calcSize() {
        if (table.length * 2 <= 4 * 1024 * 1024) {
            return table.length * 2;
        } else {
            return table.length + 4 * 1024 * 1024;
        }
    }

    private void resize() {
        int newSize = calcSize();
        Node<E>[] newTable = new Node[newSize];

        for (int i = 0; i < table.length; i++) {
            Node<E> node = table[i];
            if (node == null) {
                continue;
            }

            while (node != null) {
                Node<E> newNode = new Node<>(node.data);
                int index = node.data.hashCode() % newSize;
                Node<E> last = newTable[index];
                if (last == null) {
                    newTable[index] = newNode;
                } else {
                    while (last.next != null) {
                        last = last.next;
                    }
                    last.next = newNode;
                }

                node = node.next;
            }
        }

        table = newTable;
    }

    @Override
    public void add(E data) {
        if ((size + 1.0) / table.length >= loadFactor) {
            resize();
        }

        Node<E> node = new Node<>(data);
        int index = data.hashCode() % table.length;
        Node<E> last = table[index];
        if (last == null) {
            table[index] = node;
        } else {
            while (last.next != null) {
                last = last.next;
            }
            last.next = node;
        }
    }

    @Override
    public void remove(E data) {
        int index = data.hashCode() % table.length;
        Node<E> node = table[index];
        Node<E> pre = table[index];

        while (node != null && !node.data.equals(data)) {
            pre = node;
            node = node.next;
        }

        if (node != null) {
            pre.next = node.next;
            node.next = null;
            node = null;
        }
    }

    @Override
    public boolean contains(E data) {
        int index = data.hashCode() % table.length;

        Node<E> node = table[index];
        while (node != null) {
            if (node.data.equals(data)) {
                return true;
            }

            node = node.next;
        }

        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int index = 0;
            int visitedSize = 0;
            Node<E> node = null;

            @Override
            public boolean hasNext() {
                return visitedSize < size;
            }

            @Override
            public E next() {
                if (node == null) {
                    while (table[index] == null && index < table.length) {
                        index++;
                    }

                    node = table[index];
                }

                E data = node.data;
                node = node.next;
                return data;
            }
        };
    }
}
